{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #2 Keys Keyboard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSteps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #只有两个键的键盘"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>最初记事本上只有一个字符 <code>'A'</code> 。你每次可以对这个记事本进行两种操作：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>Copy All</code>（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。</li>\n",
    "\t<li><code>Paste</code>（粘贴）：粘贴<strong> 上一次 </strong>复制的字符。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个数字&nbsp;<code>n</code> ，你需要使用最少的操作次数，在记事本上输出 <strong>恰好</strong>&nbsp;<code>n</code>&nbsp;个 <code>'A'</code> 。返回能够打印出&nbsp;<code>n</code>&nbsp;个 <code>'A'</code> 的最少操作次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "最初, 只有一个字符 'A'。\n",
    "第 1 步, 使用 <strong>Copy All</strong> 操作。\n",
    "第 2 步, 使用 <strong>Paste </strong>操作来获得 'AA'。\n",
    "第 3 步, 使用 <strong>Paste</strong> 操作来获得 'AAA'。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [2-keys-keyboard](https://leetcode.cn/problems/2-keys-keyboard/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [2-keys-keyboard](https://leetcode.cn/problems/2-keys-keyboard/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(2,n+1):\n",
    "            dp[i]=i\n",
    "            j=2\n",
    "            while j*j<=i:\n",
    "                if i%j==0:\n",
    "                    dp[i]=dp[j]+dp[i//j]\n",
    "                    break\n",
    "                j+=1\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(2,n+1):\n",
    "            dp[i]=i\n",
    "            j=2\n",
    "            while j*j<=i:\n",
    "                if i%j==0:\n",
    "                    dp[i]=dp[j]+dp[i//j]\n",
    "                j+=1\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        buf=[0, 0, 2, 3, 4, 5, 5, 7, 6, 6, 7, 11, 7, 13, 9, 8, 8, 17, 8, 19, 9, 10, 13, 23, 9, 10, 15, 9, 11, 29, 10, 31, 10, 14, 19, 12, 10, 37, 21, 16, 11, 41, 12, 43, 15, 11, 25, 47, 11, 14, 12, 20, 17, 53, 11, 16, 13, 22, 31, 59, 12, 61, 33, 13, 12, 18, 16, 67, 21, 26, 14, 71, 12, 73, 39, 13, 23, 18, 18, 79, 13, 12, 43, 83, 14, 22, 45, 32, 17, 89, 13, 20, 27, 34, 49, 24, 13, 97, 16, 17, 14, 101, 22, 103, 19, 15, 55, 107, 13, 109, 18, 40, 15, 113, 24, 28, 33, 19, 61, 24, 14, 22, 63, 44, 35, 15, 15, 127, 14, 46, 20, 131, 18, 26, 69, 14, 23, 137, 28, 139, 16, 50, 73, 24, 14, 34, 75, 17, 41, 149, 15, 151, 25, 23, 20, 36, 20, 157, 81, 56, 15, 30, 14, 163, 45, 19, 85, 167, 16, 26, 24, 25, 47, 173, 34, 17, 19, 62, 91, 179, 15, 181, 22, 64, 29, 42, 36, 28, 51, 16, 26, 191, 15, 193, 99, 21, 18, 197, 19, 199, 16, 70, 103, 36, 24, 46, 105, 29, 21, 30, 17, 211, 57, 74, 109, 48, 15, 38, 111, 76, 20, 30, 42, 223, 17, 16, 115, 227, 26, 229, 30, 21, 35, 233, 21, 52, 63, 82, 26, 239, 16, 241, 24, 15, 65, 19, 46, 32, 37, 86, 17, 251, 17, 34, 129, 25, 16, 257, 48, 44, 22, 35, 133, 263, 20, 58, 28, 92, 71, 269, 16, 271, 25, 23, 139, 21, 30, 277, 141, 37, 18, 281, 52, 283, 75, 27, 26, 48, 16, 34, 36, 100, 77, 293, 19, 64, 43, 20, 151, 36, 17, 50, 153, 104, 27, 66, 25, 307, 22, 106, 38, 311, 22, 313, 159, 18, 83, 317, 58, 40, 17, 110, 32, 36, 16, 23, 165, 112, 47, 54, 21, 331, 87, 43, 169, 72, 18, 337, 28, 116, 26, 42, 27, 21, 49, 31, 175, 347, 36, 349, 19, 22, 21, 353, 64, 76, 93, 27, 181, 359, 17, 38, 183, 25, 24, 78, 66, 367, 31, 47, 44, 60, 38, 373, 30, 18, 53, 42, 18, 379, 28, 130, 193, 383, 17, 23, 195, 49, 101, 389, 23, 40, 20, 134, 199, 84, 21, 397, 201, 29, 18, 401, 72, 44, 105, 17, 38, 48, 26, 409, 48, 140, 107, 66, 31, 88, 23, 142, 32, 419, 19, 421, 213, 53, 59, 27, 76, 68, 111, 27, 50, 431, 17, 433, 40, 37, 113, 42, 78, 439, 22, 20, 32, 443, 44, 94, 225, 152, 19, 449, 18, 52, 117, 154, 229, 25, 28, 457, 231, 26, 32, 461, 23, 463, 37, 39, 235, 467, 23, 74, 54, 160, 65, 54, 84, 29, 28, 59, 241, 479, 18, 50, 243, 33, 26, 102, 17, 487, 67, 166, 21, 491, 48, 46, 34, 22, 39, 78, 88, 499, 19, 170, 253, 503, 19, 106, 36, 29, 131, 509, 27, 80, 18, 28, 259, 108, 50, 58, 46, 176, 24, 521, 37, 523, 135, 20, 265, 48, 22, 46, 60, 65, 30, 54, 94, 112, 73, 182, 271, 25, 18, 541, 273, 184, 27, 114, 25, 547, 141, 67, 23, 48, 32, 86, 279, 45, 143, 557, 39, 56, 20, 31, 283, 563, 54, 118, 285, 19, 77, 569, 29, 571, 28, 194, 50, 33, 18, 577, 36, 196, 38, 90, 102, 64, 79, 24, 295, 587, 21, 50, 66, 200, 45, 593, 22, 29, 153, 202, 38, 599, 19, 601, 52, 73, 155, 27, 106, 607, 29, 39, 68, 60, 27, 613, 309, 49, 24, 617, 108, 619, 40, 32, 313, 96, 24, 20, 315, 33, 161, 54, 20, 631, 85, 214, 319, 132, 60, 27, 42, 77, 19, 641, 112, 643, 34, 51, 38, 647, 18, 70, 25, 41, 167, 653, 114, 136, 49, 79, 56, 659, 23, 661, 333, 33, 89, 31, 45, 52, 171, 226, 74, 72, 20, 673, 339, 19, 30, 677, 118, 104, 28, 230, 44, 683, 29, 142, 23, 232, 51, 66, 33, 691, 177, 24, 349, 144, 38, 58, 351, 236, 21, 701, 24, 56, 23, 55, 355, 108, 66, 709, 78, 85, 95, 54, 29, 29, 183, 242, 361, 719, 19, 110, 40, 244, 185, 39, 27, 727, 26, 18, 80, 60, 68, 733, 369, 22, 33, 78, 49, 739, 46, 35, 62, 743, 40, 154, 375, 89, 32, 114, 20, 751, 55, 254, 44, 156, 20, 757, 381, 37, 30, 761, 132, 116, 195, 28, 385, 72, 19, 769, 25, 260, 197, 773, 51, 41, 103, 47, 391, 60, 25, 82, 42, 38, 22, 162, 136, 787, 201, 266, 86, 120, 23, 74, 399, 61, 203, 797, 31, 64, 20, 95, 403, 84, 74, 35, 46, 272, 107, 809, 19, 811, 40, 274, 50, 168, 28, 62, 411, 26, 50, 821, 142, 823, 109, 24, 68, 827, 33, 829, 90, 280, 25, 31, 144, 172, 34, 40, 421, 839, 21, 58, 423, 284, 215, 31, 55, 29, 61, 286, 29, 60, 78, 853, 70, 30, 113, 857, 29, 859, 52, 51, 433, 863, 19, 178, 435, 37, 42, 90, 39, 80, 115, 103, 44, 22, 80, 877, 441, 296, 24, 881, 22, 883, 34, 67, 445, 887, 46, 134, 96, 23, 227, 66, 154, 184, 21, 39, 451, 60, 20, 70, 54, 53, 119, 186, 156, 907, 231, 107, 27, 911, 30, 94, 459, 69, 233, 138, 28, 919, 34, 310, 463, 84, 25, 47, 465, 109, 39, 929, 41, 33, 237, 314, 469, 33, 25, 937, 76, 316, 56, 941, 162, 64, 67, 21, 56, 947, 86, 86, 31, 320, 30, 953, 61, 196, 243, 43, 481, 144, 20, 62, 52, 113, 245, 198, 35, 967, 28, 39, 104, 971, 19, 146, 489, 26, 69, 977, 168, 100, 23, 115, 493, 983, 50, 202, 48, 57, 36, 66, 24, 991, 41, 334, 80, 204, 90, 997, 501, 46, 21]\n",
    "        return buf[n]\n",
    "    def t(self, n: int) -> int:\n",
    "        def get_el(num):\n",
    "            t=num\n",
    "            i=2\n",
    "            ans=[]\n",
    "            while t>=i:\n",
    "                if t%i==0:\n",
    "                    ans.append(i)\n",
    "                    t=t//i\n",
    "                else:\n",
    "                    i+=1\n",
    "            return ans\n",
    "        return sum([e for e in get_el(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        def dfs(n, cur, paste):\n",
    "            if cur == n:return 0\n",
    "            if cur > n:return float(\"inf\")\n",
    "            A = B = float(\"inf\")\n",
    "            if cur != paste:A = 1 + dfs(n, cur, cur)\n",
    "            if paste:B = 1 + dfs(n, cur + paste, paste)\n",
    "            return min(A, B)\n",
    "        \n",
    "        return dfs(n, 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        def f(cur,lenth):\n",
    "            cur = cur+lenth\n",
    "            if cur == n:\n",
    "                return 1\n",
    "            ans = f(cur,lenth)+1\n",
    "            if (n-cur)%cur == 0:\n",
    "                ans = min(ans, f(cur,cur)+2)\n",
    "            return ans\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        return f(1,1)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        # cnt为操作次数，sum1为A的个数,len为当前可粘贴的长度\n",
    "        ans = 10000\n",
    "        def back(sum1, n, cnt, len1):\n",
    "            nonlocal ans\n",
    "            if sum1 == n:\n",
    "                ans = min(ans, cnt) \n",
    "                return\n",
    "            if sum1 > n:\n",
    "                return\n",
    "            # 每次加上一次的字符长度，或者当前的字符长度\n",
    "            back(sum1 + len1, n, cnt + 1, len1)\n",
    "            back(sum1 + sum1, n, cnt + 2, sum1)\n",
    "        \n",
    "        if n == 1:\n",
    "            return 0\n",
    "        back(1, n, 1, 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        @lru_cache(maxsize=None)\n",
    "        def helper(n, l, c):\n",
    "            if n == c:\n",
    "                return 0\n",
    "            if c + l == n:\n",
    "                return 1\n",
    "            if 2 * c > n or c == l:\n",
    "                return helper(n, l, c + l) + 1\n",
    "            if l == 0:\n",
    "                return helper(n, c, c) + 1\n",
    "            if n % c != 0:\n",
    "                return helper(n, l, c + l) + 1\n",
    "            r1 = helper(n, c, c)\n",
    "            r2 = helper(n, l, c + l)\n",
    "            return min(r1, r2) + 1\n",
    "        return helper(n, 0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\r\n",
    "class Solution:\r\n",
    "    def minSteps(self, n: int) -> int:\r\n",
    "        if n==1:\r\n",
    "            return 0\r\n",
    "        @lru_cache\r\n",
    "        def dfs(has_a_cnt,copy_a_cnt):\r\n",
    "            # print(has_a_cnt,copy_a_cnt)\r\n",
    "            if has_a_cnt==n:\r\n",
    "                return 0\r\n",
    "            if has_a_cnt>n:\r\n",
    "                return float('inf')\r\n",
    "            \r\n",
    "            ops=1+dfs(has_a_cnt+copy_a_cnt,copy_a_cnt)\r\n",
    "            ops=min(ops,2+dfs(has_a_cnt*2,has_a_cnt))\r\n",
    "            return ops\r\n",
    "        return 1+dfs(1,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        def dfs(cur,clip_board):\n",
    "            if cur>n:\n",
    "                return float('INF')\n",
    "            if cur==n:\n",
    "                return 0\n",
    "            return min(copy(cur,clip_board),paste(cur,clip_board))+1\n",
    "        def copy(cur,clip_board):\n",
    "            if cur==clip_board:\n",
    "                return float('INF')\n",
    "            return dfs(cur,cur)\n",
    "        def paste(cur,clip_board):\n",
    "            if not clip_board:\n",
    "                return float('INF')\n",
    "            return dfs(cur+clip_board,clip_board)\n",
    "        return dfs(1,0)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        if n == 1: return 0\n",
    "        dp = [[inf] * (n // 2 + 1) for _ in range(n + 1)]\n",
    "        dp[1][0], dp[1][1] = 0, 1\n",
    "        for i in range(2, n + 1):\n",
    "            for k in range(1, i // 2 + 1):\n",
    "                if i - k >= 0:\n",
    "                    dp[i][k] = min(dp[i][k], dp[i - k][k] + 1)\n",
    "                if k == i // 2 and i % 2 == 0:\n",
    "                    dp[i][k] = min(dp[i][k], min(dp[k]) + 2)\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur, paste):\n",
    "            if cur == n:\n",
    "                return 0\n",
    "            elif cur > n:\n",
    "                return inf\n",
    "            if paste and (n - cur) % paste:\n",
    "                return inf\n",
    "            return min(dfs(cur, cur), dfs(cur + paste, paste)) + 1 if paste and paste != cur else (dfs(cur + paste, paste) + 1 if paste else dfs(cur, cur) + 1)\n",
    "        return dfs(1, 0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(s,ram,last): # 当前值 内存值 上一步操作\n",
    "            if s==n:\n",
    "                return 0\n",
    "            if ram and (n-s)%ram!=0 or s>n:\n",
    "                return inf\n",
    "            ans = inf\n",
    "            if last!=0:\n",
    "                ans = min(ans,dfs(s,s,0)+1)\n",
    "            if ram!=0:\n",
    "                ans = min(ans,dfs(s+ram,ram,1)+1)\n",
    "            return ans\n",
    "        return dfs(1,0,-1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        inf = float('Inf')\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur, paste):\n",
    "            if cur == n:\n",
    "                return 0\n",
    "            elif cur > n:\n",
    "                return inf\n",
    "            # benhao 式剪枝\n",
    "            if paste and (n - cur) % paste:\n",
    "                return inf\n",
    "            \n",
    "            ans = inf\n",
    "            if paste:\n",
    "                ans = min(ans, dfs(cur + paste, paste) + 1)\n",
    "            \n",
    "            if cur != paste:\n",
    "                ans = min(ans, dfs(cur, cur) + 1)\n",
    "            \n",
    "            return ans \n",
    "\n",
    "        return dfs(1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        s=set()\n",
    "        unv=[['A',0,'']]\n",
    "        while(True):\n",
    "            v,cnt,p=unv.pop(0)\n",
    "            if len(v)==n:return cnt\n",
    "            if (v,p) not in s and len(v)<n:\n",
    "                s.add((v,p))\n",
    "                unv.append([v,cnt+1,v])\n",
    "                unv.append([v+p,cnt+1,p])\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        dp = [[-1] * (n+1) for _ in range(n+1)]\n",
    "        dp[1][0] = 0\n",
    "        dp[1][1] = 1\n",
    "        for i in range(2, n+1): # indicated the number of A\n",
    "            dp[i][i] = float('inf')\n",
    "            for j in range(1, i // 2 + 1): # indicated the number of copy\n",
    "                if dp[i-j][j] != -1:\n",
    "                    dp[i][j] = dp[i-j][j] + 1 # paste\n",
    "                    dp[i][i] = min(dp[i][j] + 1, dp[i][i]) # copy\n",
    "        return dp[-1][-1] - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        if n == 1: return 0\n",
    "        @cache\n",
    "        def dfs(i, p):\n",
    "            if i == n: return 0\n",
    "            elif i > n: return inf\n",
    "            if p and (n - i) % p:\n",
    "                return inf\n",
    "            if p and i != p:\n",
    "                return min(dfs(i, i), dfs(i + p, p)) + 1\n",
    "            else:\n",
    "                if p:\n",
    "                    return dfs(i + p, p) + 1\n",
    "                else:\n",
    "                    return dfs(i, i) + 1\n",
    "        return dfs(1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        #import collections\n",
    "        #memo = collections.defaultdict(dict)\n",
    "        @lru_cache(None)\n",
    "        def dfs(length, incre,count):\n",
    "            if length > n:\n",
    "                return float('inf')\n",
    "            if length == n:\n",
    "                return count\n",
    "            if incre and (n-length)%incre != 0:\n",
    "                return float('inf')\n",
    "            #if memo[length].get(incre, None) is not None:\n",
    "            #    return memo[length][incre]\n",
    "            if incre == 0:\n",
    "                ans = dfs(length, length, count+1)\n",
    "            else: \n",
    "                if length != incre:\n",
    "                    ans = min(dfs(length+incre, incre, count+1),dfs(length, length, count+1))\n",
    "                else: ans = dfs(length+incre, incre, count+1)\n",
    "            #memo[length][incre] = ans\n",
    "            return ans\n",
    "        return dfs(1,0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        dp = [[float('inf')] * (n + 1) for _ in range(n + 1)]\n",
    "        dp[1][0], dp[1][1] = 0, 1\n",
    "        ans = [float('inf')] * (n + 1)\n",
    "        ans[1] = 0\n",
    "        for j in range(1, n + 1):\n",
    "            for i in range(2 * j, n + 1, j):\n",
    "                if i == 2 * j:\n",
    "                    dp[i][j] = min(dp[i][j], ans[i - j] + 2)\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i - j][j] + 1)\n",
    "                ans[i] = min(ans[i], dp[i][j])\n",
    "        return ans[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        dp = [[float('inf')] * (n + 1) for _ in range(n + 1)]\n",
    "        dp[1][1] = 0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1,i):\n",
    "                if dp[i][j] != float('inf'):\n",
    "                    dp[i][i] = min(dp[i][i], dp[i][j])\n",
    "                    if i + j < n + 1:\n",
    "                        dp[i+j][j] = min(dp[i+j][j], dp[i][j] + 1)\n",
    "            if i == n:\n",
    "                return dp[i][i]\n",
    "            dp[i][i] += 1\n",
    "            if 2 * i < n + 1:\n",
    "                dp[2 * i][i] = min(dp[2 * i][i], dp[i][i] + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        dp = [[n] * (n+1) for __ in range(n//2+1)]\n",
    "        # print(dp)\n",
    "        for i in range(1, n//2+1):\n",
    "            for j in range(1, n+1):\n",
    "                if j < i:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    # dp[i][j] = j\n",
    "                    # print(i,j)\n",
    "                    # print(dp[i-1][j])\n",
    "                    # print( dp[i][j-i] + 2)\n",
    "                    # dp[i][j] = min(j, min(dp[i-1][j], dp[i][j-i] + 2))\n",
    "                    if j % i == 0:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i-1][i] + j//i)\n",
    "                    else:\n",
    "                        dp[i][j] = min(j, dp[i-1][j])\n",
    "        # for i in range(1, n//2+1):\n",
    "        #     # for j in range(1, n+1):\n",
    "        #     print(\" \".join(map(str, dp[i])))\n",
    "        # print(\"\")\n",
    "        return dp[ n//2][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from cmath import inf\n",
    "from functools import cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(copy: bool, paste_power: int, count: int, step: int):\n",
    "            if count == n:\n",
    "                return step\n",
    "            if count > n:\n",
    "                return inf\n",
    "            ans1 = inf\n",
    "            if not copy:\n",
    "                ans1 = dfs(True, count, count, step + 1)\n",
    "            ans2 = dfs(False, paste_power, paste_power + count, step + 1)\n",
    "            return min(ans1, ans2)\n",
    "\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        ans = dfs(1, 1, 1, 1)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        dp = [[float('inf')]*(i//2+1) for i in range(n+1)] # dp[i][j]: step to print i 'A', last time paste j 'A', j in [1, i//2]\n",
    "        dp[0][0] = 0\n",
    "        dp[1][0] = 0\n",
    "        for i in range(n+1):\n",
    "            for j in range(1, i//2+1):\n",
    "                if i-j == j:\n",
    "                    dp[i][j] = min(dp[i-j]) + 2\n",
    "                elif (i-j)//2+1 > j:\n",
    "                    dp[i][j] = dp[i-j][j] + 1\n",
    "        return min(dp[-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        dp = [[inf] * (n+1) for _ in range(n+1)]\n",
    "        dp[1][0] = 0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(i+1):\n",
    "                dp[i][i] = min(dp[i][i], dp[i][j] + 1)\n",
    "                if i+j <= n:\n",
    "                    dp[i+j][j] = min(dp[i+j][j], dp[i][j] + 1)\n",
    "        return min(dp[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 0\n",
    "        dp = [[n+1]*(n+1) for _ in range(n)]\n",
    "        for i in range(len(dp[0])):\n",
    "            dp[0][i] = 0\n",
    "        dp[1][1] = 2\n",
    "        # if 2 < len(dp[0]):\n",
    "        dp[1][2] = 3\n",
    "        for i in range(1,n):\n",
    "            for j in range(len(dp[0])):\n",
    "                if i+j < len(dp) and dp[i][j]+1 < dp[i+j][j]:\n",
    "                    dp[i+j][j] = dp[i][j]+1\n",
    "                    if i+j+1 < len(dp[0]) and i+j < n:\n",
    "                        dp[i+j][i+j+1] = min(dp[i+j][i+j+1],dp[i+j][j]+1)\n",
    "        res = 1000\n",
    "        # for i in range(len(dp)):\n",
    "        #     print(dp[i])\n",
    "        for i in dp[-1]:\n",
    "            res = min(res,i)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        dp = [[inf] * (n + 1) for _ in range(n + 1)]\n",
    "        dp[1][0] = 0; dp[1][1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(i):\n",
    "                dp[i][j] = min(dp[i][j], dp[i - j][j] + 1 if i - j >= 0 else inf)\n",
    "            dp[i][i] = min(dp[i][i], min(dp[i]) + 1)\n",
    "        return min(dp[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 0\n",
    "        sequence_lst = [[] for _ in range(n)]\n",
    "        sequence_lst[1].append(['C1','P1'])\n",
    "        for num in range(2,n):\n",
    "            for i in range(1,(num+1)//2+1):\n",
    "                for seq in sequence_lst[num-i]:\n",
    "                    if seq[-1] == f'P{i}':\n",
    "                        sequence_lst[num].append(seq+[f'P{i}'])\n",
    "                if num+1-i == i:\n",
    "                    sequence_lst[num].append(sequence_lst[num-i][0]+[f'C{i}',f'P{i}'])\n",
    "            sequence_lst[num].sort(key = lambda x: len(x))\n",
    "        return len(sequence_lst[n-1][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        if n <= 1:\n",
    "            return 0\n",
    "        dp = [[sys.maxsize for _ in range(n+1)] for _ in range(n+1)]\n",
    "        dp[1][1] = 0\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(1, i//2+1):\n",
    "                if i == 2 * j:\n",
    "                    if min(dp[j][:]) != sys.maxsize:\n",
    "                        dp[i][j] = min(dp[j][:]) + 2\n",
    "                else:\n",
    "                    if dp[i-j][j] != sys.maxsize:\n",
    "                        dp[i][j] = dp[i-j][j] + 1\n",
    "        return min(dp[n][:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "       \n",
    "        dp = [[n for _ in range(n+1)] for _ in range(n+1)]\n",
    "\n",
    "        for i in range(n+1):\n",
    "            dp[n][i] = 0\n",
    "\n",
    "        for cur in range(n-1, -1, -1):\n",
    "            for pre in range(cur, -1, -1):\n",
    "                res = min(dp[cur][pre], 1 + dp[cur][cur])\n",
    "                if cur + pre <= n:\n",
    "                    res = min(res, 1 + dp[cur+pre][pre])\n",
    "                dp[cur][pre] = res\n",
    "\n",
    "        return dp[1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        inf = float('inf')\n",
    "        dp = [[inf] * (n + 1) for _ in range(n + 1)]\n",
    "        dp[1][0] = 0\n",
    "        dp[1][1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                if i % j != 0: continue\n",
    "                if j != i:\n",
    "                    dp[i][j] = dp[i - j][j] + 1\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i]) + 1\n",
    "        return min(dp[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        if n == 1: return 0\n",
    "        store =dict()\n",
    "        ret = [1001]\n",
    "        def get(cur,cp,st):\n",
    "            if cur > n or st > ret[0]: return\n",
    "            if (cur,cp) in store and store[(cur,cp)] < st:\n",
    "                return\n",
    "            if cur ==n: \n",
    "                ret[0] = min(st,ret[0])\n",
    "                return\n",
    "            store[(cur,cp)] = st\n",
    "\n",
    "            get(cur+cp,cp ,st+1)\n",
    "            get(cur   ,cur,st+1)\n",
    "\n",
    "        get(1,0,0)\n",
    "\n",
    "        return ret[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        inf = 10**9\n",
    "        dp = [[inf for _ in range(n+1)] for _ in range(n+1)]\n",
    "        dp[0][0] = 0\n",
    "        dp[1][0] = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1):\n",
    "                if dp[i][j] != inf:\n",
    "                    if i+j<=n:\n",
    "                        dp[i+j][j] = min(dp[i+j][j], dp[i][j]+1)\n",
    "                    dp[i][i] = min(dp[i][i], dp[i][j]+1)\n",
    "        return min(dp[n][j] for j in range(n+1))\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        def dfs(cnt, copy, path, vis):\n",
    "            if cnt == n:\n",
    "                return path\n",
    "            if cnt > n:\n",
    "                return 10 ** 6\n",
    "            if vis[cnt][copy] != -1:\n",
    "                return vis[cnt][copy]\n",
    "            ans = n + 1\n",
    "            ans = min(ans, dfs(cnt * 2, cnt, path + 2, vis))\n",
    "            if copy > 0:\n",
    "                ans = min(ans, dfs(cnt + copy, copy, path + 1, vis))\n",
    "            vis[cnt][copy] = ans\n",
    "            return ans\n",
    "\n",
    "        vis = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "        return dfs(1, 0, 0, vis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        # copy+past or past\n",
    "        memo = {}\n",
    "\n",
    "        def dp(a_window, a_paste):\n",
    "            if (a_window, a_paste) in memo:\n",
    "                return memo[(a_window, a_paste)]\n",
    "            #当前屏幕上有a_window个'A'，粘贴板上有a_paste个'A', 目标是target, 返回需要的最少操作次数\n",
    "\n",
    "            if a_window == n:\n",
    "                return 0\n",
    "\n",
    "            elif a_window > n:\n",
    "                return float('inf')\n",
    "\n",
    "            if a_paste > 0:\n",
    "                memo[(a_window, a_paste)] = min(1+dp(a_window+a_paste, a_paste), 2+dp(2*a_window, a_window))\n",
    "            else:\n",
    "                memo[(a_window, a_paste)] = 2+dp(2*a_window, a_window)\n",
    "\n",
    "            return memo[(a_window, a_paste)]\n",
    "\n",
    "        return dp(1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        inf = n\n",
    "\n",
    "        save = {}\n",
    "        def f(i,j):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            if i > n:\n",
    "                return n\n",
    "            if i + j > n:\n",
    "                return n\n",
    "            if i + j == n:\n",
    "                return 1    \n",
    "            kk = (i,j)\n",
    "            ans = save.get(kk)\n",
    "            if ans is not None:\n",
    "                return ans\n",
    "            ans = n\n",
    "            if i != j:\n",
    "                ans = min(ans, f(i,i) + 1) \n",
    "            if j > 0:\n",
    "                ans = min(ans, f(i+j,j) + 1)\n",
    "            save[kk] = ans\n",
    "            return ans\n",
    "        \n",
    "        return f(1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n):\n",
    "        memo = {}\n",
    "        def dfs(i, paste): # i: what's on the screen; paste: what's ready for paste\n",
    "            if (i, paste) in memo:\n",
    "                return memo[(i, paste)]\n",
    "            if i == n:  # found a solution\n",
    "                return 0\n",
    "            if i > n or i + paste > n:  # won't lead to a solution, so we stop.\n",
    "                return float('inf')\n",
    "\n",
    "            # try pasting, if we have something to paste\n",
    "            new_paste = 1 + dfs(i + paste, paste) if paste > 0 else float('inf')\n",
    "\n",
    "            # try copying, if what we have on the board is > what we have copied\n",
    "            # 第二个if(copy_A >= current_A) 可能换成 if(copy_A == current_A)会更好理解一点, 即如果剪切板中A的个数==现有A的个数, 则无需重复copyall, 继续paste即可. 因为剪切板中的A个数是不会超过现有A的个数的。\n",
    "            new_copy = 1 + dfs(i, i) if i != paste else float('inf') # if i > paste else float('inf')\n",
    "\n",
    "            memo[(i, paste)] = min(new_paste, new_copy)\n",
    "            return memo[(i, paste)]\n",
    "\n",
    "        # start with 1 A on the board and 0 copied\n",
    "        return dfs(1, 0)\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def minSteps(self, n: int) -> int:\n",
    "#         dp = [0] * (n + 1) # 最后n个a的最少步骤。注意要取得n,所以到n+1\n",
    "#         for i in range(2, n + 1): # i: current n：n=1 return 0已知0.从2开始算\n",
    "#             dp[i] = i # 如果i本身是质数，没法拆分，只能paste i次,下面那个for loop不会run\n",
    "#             # 2: 2or2之后才能找质因子\n",
    "#             for j in range(2, int(sqrt(i)) + 1): # 优化\n",
    "#             # for j in range(2, si): # j: number of character can be copy or paste\n",
    "#                 if i % j == 0: # 找到1个质因子对j & i//j，就不用找了\n",
    "#                     dp[i] = dp[j] + dp[i//j]  # copy + paste \n",
    "#                     break\n",
    "#         return dp[-1]\n",
    "\n",
    "\"\"\"\n",
    "n=1 return 0 since you don't need do anything\n",
    "eg1: n=6\n",
    "step 1: copy A\n",
    "step 2: paste A: AA\n",
    "step 3: copy AA\n",
    "step 4: paste AA: AAAA\n",
    "step 5: paste AA: AAAAAA  # paste 就是copy all的乘法操作。 2copy*3paste = 6(就是分解质因子)\n",
    "\n",
    "OR\n",
    "step 1: copy A\n",
    "step 2: paste A: AA\n",
    "step 3: paste A: AAA\n",
    "step 4: copy AAA:\n",
    "step 5: paste AAA: AAAAAA\n",
    "\n",
    "note: you can copy all and then paste multiple times\n",
    "\n",
    "eg2: n=12\n",
    "2*6 = 12\n",
    "3*4 =12 that is 3copy 4 paste\n",
    "但是dp[12] = dp[2] + dp[6] 找到就可以break了。因为这里是dp[6]，就是最优的dp解\n",
    "\n",
    "# for j in range(2, int(sqrt(i)) + 1):\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        cache = {}\n",
    "\n",
    "        def backtrack(pre, cnt):\n",
    "            if cnt == n:\n",
    "                return 1\n",
    "            if cnt > n:\n",
    "                return float('inf')\n",
    "            if cnt in cache:\n",
    "                return cache[(pre, cnt)]\n",
    "            mins = float('inf')\n",
    "            mins = min(backtrack(pre, pre + cnt), mins)\n",
    "            if pre != cnt:\n",
    "                mins = min(backtrack(cnt, cnt + cnt)+1, mins)\n",
    "            cache[(pre, cnt)] = mins+1\n",
    "            return mins+1\n",
    "        return backtrack(1, 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        memo = {}\n",
    "        def dfs(i, paste):\n",
    "            if (i, paste) in memo:\n",
    "                return memo[(i, paste)]\n",
    "            if i == n:\n",
    "                return 0\n",
    "            if i > n or i + paste > n:\n",
    "                return float('inf')\n",
    "            new_copy = 1 + dfs(i, i) if i != paste  else float('inf')\n",
    "            new_paste = 1 + dfs(i + paste, paste) if paste > 0 else float('inf')\n",
    "            memo[(i, paste)] = min(new_copy, new_paste)\n",
    "            return memo[(i, paste)]\n",
    "        return dfs(1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n):\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        f = [[float(\"inf\")] * (n + 1) for _ in range(n + 1)]\n",
    "        f[1][1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(1, math.floor(i / 2) + 1):\n",
    "                f[i][j] = f[i - j][j] + 1\n",
    "            f[i][i] = min(f[i]) + 1\n",
    "        return f[n][n] - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "\n",
    "        if n == 1:\n",
    "            return 0\n",
    "\n",
    "        memo = dict()\n",
    "        \n",
    "        def foo(cur, cur_copy):\n",
    "            if cur == n:\n",
    "                return 1\n",
    "            if cur > n:\n",
    "                return math.inf\n",
    "            \n",
    "            if cur not in memo:\n",
    "                memo[(cur, cur_copy)] = min(1 + foo(cur+cur_copy, cur_copy), 2 + foo(cur+cur, cur))\n",
    "\n",
    "            return memo[(cur, cur_copy)]\n",
    "\n",
    "\n",
    "        return foo(1, 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        @cache\n",
    "        def f(last, cur, copy):\n",
    "            if last == 0:\n",
    "                return 0\n",
    "            if last == copy:\n",
    "                return 1\n",
    "            if last == cur:\n",
    "                return 2\n",
    "            if copy > last:\n",
    "                return 10**6\n",
    "            return min(f(last-copy, cur+copy, copy)+1,\n",
    "            f(last-cur, cur+cur, cur)+2)\n",
    "        return f(n-1, 1, 1)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        import numpy as np\n",
    "        if n <= 1:\n",
    "            return 0\n",
    "        for i in range(2, int(sqrt(n)) + 1):\n",
    "            if n % i == 0:\n",
    "               return self.minSteps(n // i) + i\n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    # 精选题解：暴力搜索，自己想 dp 没想出来，其实应该先想想暴力搜索\n",
    "    #   @思路：\n",
    "    #       1. 对于每一次迭代都有两个选择，可以进行「复制」或「粘贴」，若为复制，则只需将当前的所有字符拷贝到剪切板，粘贴则是将剪切板的字符加上当前字符，可以定义 dfs 函数，参数为当前字符数 cur 和当前剪切板的字符数 clip\n",
    "    #       2. 递归终止条件：当 cur == n 时，返回 0，表示搜索成功；若 cur > n 则表示已经超出了，不合理，则直接返回 math.inf\n",
    "    #       3. 搜索：选择「复制」和「搜索」两种选择的最小值\n",
    "    #           1. 复制：只有在上一次操作不是复制时，才可以复制，否则会导致无限递归，因为可以一直复制。只需将 clip 部分等于 cur\n",
    "    #           2. 粘贴：将 cur+clip 即可\n",
    "    #       4. 初始状态：cur 为 1，因为记事本中有一个 A，剪切板中没有\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        def dfs(cur: int, clip: int) -> int:\n",
    "            if cur == n: return 0\n",
    "            if cur > n: return math.inf\n",
    "\n",
    "            res = math.inf\n",
    "            # 复制，只有上一次不是操作才能复制，否则会无限递归\n",
    "            if cur != clip:\n",
    "                res = min(res, dfs(cur, cur)+1)\n",
    "            # 粘贴\n",
    "            if clip != 0:\n",
    "                res = min(res, dfs(cur+clip, clip)+1)\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return dfs(1, 0)\n",
    "    \n",
    "    # 记忆化搜索\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        memo = dict()\n",
    "        def dfs(cur: int, clip: int) -> int:\n",
    "            if cur == n: return 0\n",
    "            if cur > n: return math.inf\n",
    "            if (cur, clip) in memo: return memo[(cur, clip)]\n",
    "\n",
    "            res = math.inf\n",
    "            # 复制，只有上一次不是操作才能复制，否则会无限递归\n",
    "            if cur != clip:\n",
    "                res = min(res, dfs(cur, cur)+1)\n",
    "            # 粘贴\n",
    "            if clip != 0:\n",
    "                res = min(res, dfs(cur+clip, clip)+1)\n",
    "            memo[(cur, clip)] = res\n",
    "            return res\n",
    "        \n",
    "        return dfs(1, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "\n",
    "        def can_success(now: int, copy: int, goal: int):\n",
    "            if (now, copy) in memo:\n",
    "                return memo[(now, copy)]\n",
    "            elif now == goal:\n",
    "                return 0\n",
    "            elif now > goal:\n",
    "                return 9999\n",
    "            else:\n",
    "                flag1 = goal\n",
    "                flag2 = goal\n",
    "                if now != copy:\n",
    "                    flag1 = 1 + can_success(now, now, goal) #复制\n",
    "                if copy != 0:\n",
    "                    flag2 = 1 + can_success(now + copy, copy, goal) #粘贴\n",
    "                memo[(now, copy)] = min(flag1, flag2)\n",
    "                return memo[(now, copy)]\n",
    "        \n",
    "        memo = {}\n",
    "        return can_success(1, 0, n)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        def helper(cur,memory,target_n,cnt):\n",
    "            tmp=cur+memory\n",
    "            # print(tmp)\n",
    "            if tmp==target_n:\n",
    "                # print(\"rrr\")\n",
    "                return cnt\n",
    "            elif tmp<target_n:\n",
    "                cnt=min(helper(tmp,memory,target_n,cnt+1),helper(tmp,tmp,target_n,cnt+2))\n",
    "            else:\n",
    "                cnt=float(\"inf\")\n",
    "            return cnt\n",
    "        if n<=1:\n",
    "            return 0\n",
    "        return helper(1,1,n,cnt=2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "\n",
    "        def min_step(s: int, k: int, n: int) -> int:\n",
    "            if (s, k) in memo:\n",
    "                return memo[(s, k)]\n",
    "            elif s == n:\n",
    "                return 0\n",
    "            elif s > n:\n",
    "                return n\n",
    "            else:\n",
    "                if k == 0:\n",
    "                    memo[(s, k)] = 1 + min_step(s, s, n)\n",
    "                elif s == k:\n",
    "                    memo[(s, k)] = 1 + min_step(s + k, k, n)\n",
    "                else:\n",
    "                    memo[(s, k)] = 1 + min(min_step(s, s, n), min_step(s + k, k, n))\n",
    "                return memo[(s, k)]\n",
    "        \n",
    "        memo = {}\n",
    "        return min_step(1, 0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        f = [[float('inf')] * (n+1) for _ in range(n+1)]\n",
    "        f[1][0] = 0\n",
    "        f[1][1] = 1\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(1, i+1):\n",
    "                if i - j >= j:\n",
    "                    f[i][j] = f[i-j][j] + 1\n",
    "                else:\n",
    "                    break\n",
    "                f[i][i] = min(f[i][i], f[i][j] + 1)\n",
    "        \n",
    "        return min(f[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        f = [[inf] * (n + 1) for _ in range(n + 1)]\n",
    "        f[1][0] = 0\n",
    "        f[1][1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            mi = inf\n",
    "            for j in range(i // 2 + 1):\n",
    "                f[i][j] = f[i - j][j] + 1\n",
    "                mi = min(mi, f[i][j])\n",
    "            f[i][i] = mi + 1\n",
    "        return min(f[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps_DFS(self, n: int) -> int: # (26.08,11.05)\n",
    "        def DFS(cur_num, cur_copy, cur_steps):\n",
    "            nonlocal ans\n",
    "            if cur_num == n:\n",
    "                ans = min(ans, cur_steps)\n",
    "                return\n",
    "            elif cur_num > n:\n",
    "                return\n",
    "            if cur_num <= n / 2:\n",
    "                DFS(cur_num * 2, cur_num, cur_steps + 2)\n",
    "            DFS(cur_num + cur_copy, cur_copy, cur_steps + 1)\n",
    "            \n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 2\n",
    "        inf = float('inf')\n",
    "        ans = inf\n",
    "        DFS(2, 1, 2)\n",
    "        return ans\n",
    "    \n",
    "    def minSteps(self, n: int) -> int:\n",
    "        inf = float('inf')\n",
    "        dp = [[inf] * (n + 1) for _ in range(n + 1)]\n",
    "        dp[1][0] = 0\n",
    "        dp[1][1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            the_min = inf\n",
    "            for j in range((i >> 1) + 1):\n",
    "                dp[i][j] = dp[i - j][j] + 1\n",
    "                the_min = min(the_min, dp[i][j])\n",
    "            dp[i][i] = the_min + 1\n",
    "        return min(dp[-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        memo = {}\n",
    "        def process(have, copy):\n",
    "            if have == n:\n",
    "                return 0\n",
    "\n",
    "            if have > n:\n",
    "                return float(\"inf\")\n",
    "\n",
    "            if (have, copy) in memo:\n",
    "                return memo[(have, copy)]\n",
    "            \n",
    "            res = float(\"inf\")\n",
    "            # 复制全部，不能连续复制、复制操作，不然就会进入死循环\n",
    "            if copy != have:\n",
    "                res = 1 + process(have, have)\n",
    "            # 粘贴\n",
    "            if copy:\n",
    "                res = min(res, 1 + process(have+copy, copy))\n",
    "\n",
    "            memo[(have, copy)] = res\n",
    "            return res\n",
    "\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        return process(1, 1) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        @cache\n",
    "        def minStepsC(n, k_num):\n",
    "            if k_num > n:\n",
    "                return inf\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            if n <= 0:\n",
    "                return inf\n",
    "            if k_num == n:\n",
    "                last_k_max = n // 2\n",
    "                return min([minStepsC(n, k) + 1 for k in range(1, last_k_max + 1)])\n",
    "            return minStepsC(n - k_num, k_num) + 1\n",
    "       \n",
    "        # print(minStepsC(5,1))\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        return min([minStepsC(n, k) for k in range(1, n)]) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "\n",
    "        dp = [[inf]*(n+1) for _ in range(n+1)]\n",
    "        dp[1][0] = 0\n",
    "        dp[1][1] = 1\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            curmin = inf\n",
    "            for j in range(i//2+1):\n",
    "                dp[i][j] = dp[i-j][j] + 1\n",
    "                curmin = min(curmin, dp[i][j])\n",
    "            dp[i][i] = curmin + 1\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(n+1):\n",
    "            ans = min(dp[-1][i], ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        dp = [[1001]*(n + 1) for _ in range(1 + n)]\n",
    "        dp[1][1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i][i] = 1001\n",
    "            for j in range(1, i//2 + 1):\n",
    "                dp[i][j] = dp[i - j][j] + 1\n",
    "                dp[i][i] = min(dp[i][i], 1 + dp[i][j])\n",
    "        print(dp[n])\n",
    "        return min(dp[n][1: ])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(cur,in_paste):\n",
    "            if cur == 0:\n",
    "                return 0\n",
    "            res = 0x3f3f3f3f\n",
    "            if in_paste < n - cur:\n",
    "                res = min(res,dfs(cur,n - cur ) + 1)\n",
    "            if in_paste > 0 and cur >= in_paste:\n",
    "                res = min(res,dfs(cur - in_paste,in_paste) + 1)\n",
    "            return res\n",
    "        return dfs(n - 1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        @functools.cache\n",
    "        def min_steps(cur_len, paste_len):\n",
    "            if cur_len == n:\n",
    "                return 0\n",
    "            if paste_len == 0:\n",
    "                return min_steps(cur_len, cur_len) + 1\n",
    "            ans = float('inf')\n",
    "            if cur_len + paste_len <= n:\n",
    "                ans = min(ans, min_steps(cur_len + paste_len, paste_len)+1)\n",
    "            if cur_len != paste_len:\n",
    "                ans = min(ans, min_steps(cur_len, cur_len)+1)\n",
    "            return ans\n",
    "        return min_steps(1, 0)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        dp = [0 for i in range(n + 1)]\n",
    "        h = int(np.sqrt(n))\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = i\n",
    "            for j in range(1, h+1):\n",
    "                if i % j == 0:\n",
    "                    dp[i] = dp[j] + dp[int(i/j)]\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(curTotalA: int, curCopyA: int):\n",
    "            if curTotalA == n:\n",
    "                return 0\n",
    "            if curTotalA > n:\n",
    "                return float('inf')\n",
    "            t1 = dfs(curTotalA + curCopyA, curCopyA) + 1  # 只paste\n",
    "            t2 = dfs(curTotalA * 2, curTotalA) + 2  # copy all了之后再paste\n",
    "            return min(t1, t2)\n",
    "        \n",
    "        # 如果n>1，那么要避免一直paste empty的情况，所以这里要加1（已经copy all了一次），并且curPoyA设为1\n",
    "        return 1 + dfs(1, 1) if n > 1 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        if n == 1: return 0\n",
    "        @cache\n",
    "        def dfs(tot: int, pre: int) -> int:\n",
    "            if tot == n:\n",
    "                return 0\n",
    "            if n - tot < pre:\n",
    "                return inf\n",
    "            if tot == pre:\n",
    "                return dfs(tot + pre, pre) + 1\n",
    "            return min(dfs(tot + pre, pre), dfs(tot, tot)) + 1\n",
    "        return dfs(1, 1) + 1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        \n",
    "        @cache\n",
    "        def dfs(num, c) :\n",
    "            if num >= n :\n",
    "                return 1 if num == n else inf\n",
    "            return min(dfs(num+c, c) + 1, dfs(num+num, num) + 2)\n",
    "        \n",
    "        return dfs(1, 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(cur_A, mem_A):\n",
    "            if cur_A == n: return 0\n",
    "            if cur_A + mem_A == n: return 1\n",
    "            if cur_A + mem_A > n: return 10 ** 9\n",
    "\n",
    "            res = 10 ** 9\n",
    "            if mem_A != cur_A:\n",
    "                res = dfs(cur_A, cur_A) + 1\n",
    "            if mem_A:\n",
    "                res = min(res, dfs(cur_A + mem_A, mem_A) + 1)\n",
    "            return res\n",
    "        return dfs(1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        vis = set()\n",
    "        def process(have, copy):\n",
    "            if have == n:\n",
    "                return 0\n",
    "\n",
    "            if have > n:\n",
    "                return float(\"inf\")\n",
    "\n",
    "            if (have, copy) in vis:\n",
    "                return float(\"inf\")\n",
    "\n",
    "            vis.add((have, copy))\n",
    "\n",
    "            # 复制全部\n",
    "            res = 1 + process(have, have)\n",
    "            # 粘贴\n",
    "            if copy:\n",
    "                res = min(res, 1 + process(have+copy, copy))\n",
    "            return res\n",
    "\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        return process(1, 1) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        dp = [[float('inf') for paste in range(n // 2 + 1)] for num in range(n + 1)]\n",
    "        # dp[num][paste] 可以粘贴paste的情况下，到达num的最少操作数\n",
    "        dp[1][0] = 0\n",
    "        dp[1][1] = 1\n",
    "        for num in range(2, n + 1):\n",
    "            minVal = float('inf')\n",
    "            for paste in range(1, num // 2 + 1):\n",
    "                dp[num][paste] = min(\n",
    "                    dp[num][paste],\n",
    "                    dp[num - paste][paste] + 1\n",
    "                )\n",
    "                minVal = min(dp[num][paste], minVal)\n",
    "            if num < n // 2 + 1:\n",
    "                dp[num][num] = minVal + 1\n",
    "        return min(dp[-1][paste] for paste in range(n // 2 + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        @functools.cache\n",
    "        def dfs(target, paste):\n",
    "            if target > n:\n",
    "                return 100000\n",
    "            if target == n:\n",
    "                return 0\n",
    "            return min(dfs(2 * target, target) + 2, dfs(target + paste, paste) + 1)\n",
    "\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        return dfs(1, 1) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(curr, op, l):\n",
    "            if curr == n:\n",
    "                return 1\n",
    "\n",
    "            ans = float('inf')\n",
    "            if op == 1:\n",
    "                ans = min(ans, dfs(curr, 0, curr) + 1)\n",
    "            if curr + l <= n:\n",
    "                ans = min(ans, dfs(curr + l, 1, l) + 1)\n",
    "            return ans\n",
    "\n",
    "        ans = dfs(1, 0, 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j):\n",
    "            if i > n:\n",
    "                return n\n",
    "            elif i==n:\n",
    "                return 0\n",
    "            ans = n \n",
    "            if j > 0:\n",
    "                ans = min(ans,dfs(i+j,j))\n",
    "            if i > j:\n",
    "                ans = min(ans,dfs(i,i))\n",
    "            return ans + 1\n",
    "        return dfs(1,0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        if n == 1: return 0\n",
    "        # Note first step must be copy.\n",
    "        # Let dp[i][j][k] be min number of operations left\n",
    "        # if there are i characters on screen,\n",
    "        # j characters remaining, k characters copied.\n",
    "        # Note that only need to consider when k <= i.\n",
    "\n",
    "        # Base case: dp[i][j][j] = 1, dp[i][j][k] = inf if k > j.\n",
    "        # Consider dp[i][j][k] where k < j.\n",
    "        # There are two choices: copy and paste.\n",
    "        # If copy, dp[i][j][k] = 1 + dp[i][j][i]\n",
    "        # If paste, dp[i][j][k] = 1 + dp[i+k][j-k][k]\n",
    "        # dp[i][j][k] = min(dp[i][j][i], dp[i+k][j-k][k]) + 1\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j, k):\n",
    "            if j == k: return 1\n",
    "            if k > j: return float('inf')\n",
    "            # No need to copy.\n",
    "            if k == i: return dfs(i + k, j - k, k) + 1\n",
    "            return min(dfs(i, j, i), dfs(i + k, j - k, k)) + 1\n",
    "        \n",
    "        return dfs(1, n - 1, 1) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        @cache\n",
    "        def getNum(existing, copyMap):\n",
    "            if existing == n:\n",
    "                return 0\n",
    "            if existing > n:\n",
    "                return inf\n",
    "            if copyMap == 0:\n",
    "                return 1+getNum(existing, existing)\n",
    "            if copyMap == existing:\n",
    "                return 1+getNum(existing+copyMap, copyMap)\n",
    "            return min(1+getNum(existing+copyMap, copyMap), 1+getNum(existing, existing))\n",
    "        return getNum(1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        '''\n",
    "        动态规划思路，f[i][j]为经过最后一次操作后，记事本上有i个字符，粘贴板上有j个字符的最小操作数\n",
    "        j <= i\n",
    "        1.最后paste f[i][j] = f[i-j][j] + 1\n",
    "        2.最后copy all f[i][j] = min(f[i][x]+1)\n",
    "        '''\n",
    "        import sys\n",
    "        INF = sys.maxsize\n",
    "        f = [[INF for _ in range(n+1)] for _ in range(n+1)] \n",
    "        f[1][0] = 0\n",
    "        f[1][1] = 1\n",
    "        for i in range(2, n+1):\n",
    "            tmp = INF\n",
    "            for j in range(i // 2 + 1):\n",
    "                f[i][j] = f[i-j][j] + 1\n",
    "                tmp = min(tmp, f[i][j])\n",
    "            f[i][i] = tmp + 1\n",
    "        return min(f[n])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(s,ram,last): # 当前值 内存值 上一步操作\n",
    "            if s==n:\n",
    "                return 0\n",
    "            if s>n:\n",
    "                return inf\n",
    "            ans = inf\n",
    "            if last!=0:\n",
    "                ans = min(ans,dfs(s,s,0)+1)\n",
    "            if ram!=0:\n",
    "                ans = min(ans,dfs(s+ram,ram,1)+1)\n",
    "            return ans\n",
    "        return dfs(1,0,-1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "\n",
    "        # O(n^2)\n",
    "        # O(n^2)\n",
    "\n",
    "        if n == 1: return 0\n",
    "\n",
    "        @cache\n",
    "        def dp(copy, cur):\n",
    "            if cur > n: return float(\"inf\")\n",
    "            if cur == n: return 0\n",
    "            res = float(\"inf\")\n",
    "            if copy == cur:\n",
    "                res = min(res, dp(copy, cur*2)+1)\n",
    "            else:\n",
    "                res = min(res, dp(copy, cur+copy)+1)\n",
    "                res = min(res, dp(cur, cur)+1)\n",
    "            return res\n",
    "        \n",
    "        return dp(1, 1) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dp(have, copied) :\n",
    "            if have == n :\n",
    "                return 0\n",
    "            if have > n :\n",
    "                return n\n",
    "            res = n\n",
    "            if copied != have :\n",
    "                res = dp(have, have) + 1\n",
    "            if copied > 0 :\n",
    "                res = min(res, dp(have + copied, copied) + 1)\n",
    "            return res\n",
    "        \n",
    "        return dp(1, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "\n",
    "        # # 方法1：两次遍历的DP\n",
    "        # if n == 0: return False\n",
    "        # if n == 1: return 0\n",
    "        dp = [[1000 for _ in range(n+1)] for _ in range(n+1)]\n",
    "        dp[1][0] = 0 # 已经有了1个字符，copy版上有0个字符（初始状态）\n",
    "        dp[1][1] = 1 # 已经有了1个字符，copy板上有1个字符（初始状态+copy）\n",
    "        # dp[i][j] 表示对于i个字符，且copy了j个字符的情况下，所需要的操作次数\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(1, i):\n",
    "                dp[i][j] = dp[i-j][j] + 1\n",
    "                dp[i][i] = min(dp[i][j] + 1, dp[i][i])\n",
    "        return min(dp[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dp(t, clip):\n",
    "            if t == n: return 0\n",
    "            if t > n: return n\n",
    "            if t == clip: return 1 + dp(t+clip, clip)\n",
    "            if clip == 0: return 1 + dp(t, t)\n",
    "            return 1 + min(dp(t, t), dp(t+clip, clip)) \n",
    "        return dp(1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        ###do[i][j]表示当前字符为i个，剪切板字符为j个时的最少操作次数\n",
    "        dp = [[float('inf')]*(n+1) for _ in range(n+1)]\n",
    "        dp[1][0] = 0\n",
    "        dp[1][1] = 1\n",
    "        for i in range(2, n+1):\n",
    "            min_v = float('inf')\n",
    "            for j in range(1, i+1): \n",
    "                if i != j:\n",
    "                    dp[i][j] = dp[i-j][j]+1 #paste\n",
    "                    min_v = min(min_v, dp[i][j])  ###  1 <= j <= i\n",
    "                else:  ##copy i == j\n",
    "                    dp[i][j] = min_v + 1\n",
    "        return min(dp[n])\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        \n",
    "        @cache\n",
    "        def dfs(x: int, y: 0) -> int:\n",
    "            if x == n:\n",
    "                return 0\n",
    "            if x > n or y > n:\n",
    "                return inf\n",
    "            res = dfs(x + y, y)\n",
    "            if x != y:\n",
    "                res = min(res, dfs(x, x))\n",
    "            return res + 1\n",
    "        return dfs(1, 1) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        # 记事本上有x个A,复制板有y个A\n",
    "        @cache\n",
    "        def f(x,y)->int:\n",
    "            if x == n:return 0\n",
    "            if x > n: return 1001\n",
    "            if y == 0: return 1+f(x,x)\n",
    "            if y == x: return 1+f(x+y,y)\n",
    "            return min(1+f(x+y,y),1+f(x,x))\n",
    "\n",
    "        return f(1,0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        dp = [[0x3f3f3f3f for j in range(n+1)] for i in range(n+1)]\n",
    "        dp[1][0] = 0\n",
    "        dp[1][1] = 1\n",
    "        for i in range(2, n+1):\n",
    "            minJ = 0x3f3f3f3f\n",
    "            for j in range(i):\n",
    "                dp[i][j] = dp[i-j][j]+1\n",
    "                minJ = min(minJ, dp[i][j])\n",
    "            dp[i][i] = minJ + 1\n",
    "        return min(dp[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSteps(self, n: int) -> int:\n",
    "        # dp[n][a] 表示n个字符，剪贴板a的最小操作\n",
    "        # dp[n][a]=dp[n-a][a]+1\n",
    "        # dp[n][n]=min_a(dp[n][a])+1\n",
    "        dp=[[inf]*(n+1) for _ in range(n+1)]\n",
    "        dp[1][0]=0\n",
    "        dp[1][1]=1\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(1,i):\n",
    "                dp[i][j]=dp[i-j][j]+1\n",
    "                dp[i][i]=min(dp[i][j]+1,dp[i][i])\n",
    "        return min(dp[n])\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
